#include<bits/stdc++.h>
#define int long long 
using namespace std;
int mod,T;
int n,m,ans;
int f[4000005];
inline int poww(int x,int y){
	int sum=1;
	while(y){
		if(y&1)sum=(sum*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return sum;
}
signed main(){
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
	scanf("%lld %lld",&mod,&T);
	while(T--){
		for(int i=0;i<=n*m;i++)f[i+1]=0;
		ans=0;
		scanf("%lld %lld",&n,&m);
		f[1]=1;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=i*m;j++)f[j+1]=(f[j+1]+f[j])%mod;
			for(int j=i*m;j>=0;j--)f[j+1]=(f[j+1]-f[max(0ll,j-m)]+mod)%mod;
		}
		for(int i=0;i<=n*m;i++)ans=(ans+f[i+1]*f[i+1])%mod;
		printf("%lld\n",((poww(m+1,2*n)-ans+mod)%mod)  * (poww(poww(m+1,2*n),mod-2)*poww(2,mod-2)%mod)%mod);
	}
	return 0;
} 
